package leecode

import "sort"

func minimumTotal(triangle [][]int) int {
	dp := make([][]int, len(triangle)) //dp数组为走到i,j位置上时的最小路径和
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, len(triangle[i]))
	}
	//初始化dp数组
	dp[0][0] = triangle[0][0]
	for i := 1; i < len(triangle); i++ {
		for j := 0; j < len(triangle[i]); j++ {
			if j == 0 {
				dp[i][j] = triangle[i][j] + dp[i-1][j]
			} else if i == j {
				dp[i][j] = dp[i-1][j-1] + triangle[i][j]
			} else {
				dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
			}
		}
	}
	sort.Ints(dp[len(dp)-1])
	temp := dp[len(dp)-1]
	return temp[0]
}
